//
// Description: 144. 二叉树的前序遍历
// Created by Loading on 2021/5/2.
//

#include <bits/stdc++.h>
#include "Data_Structure_Definition.h"

using namespace std;

/* 递归算法 */
void preorderInternal(vector<int> &res, TreeNode *root) {
    if (!root) {
        return;
    }
    res.emplace_back(root->val);
    preorderInternal(res, root->left);
    preorderInternal(res, root->right);
}

vector<int> preorderTraversal(TreeNode *root) {
    vector<int> res;
    preorderInternal(res, root);

    return res;
}

/* 迭代算法 */
vector<int> preorderTraversal_Iteratively(TreeNode *root) {
    vector<int> res;
    //维护一个栈
    stack<TreeNode *> stk;
    /* 栈为空且root为nullptr，表示遍历完毕 */
    /* 栈为空，root不为nullptr，表示开始遍历根节点右子树 */
    /* 栈不为空，root为nullptr，表示遍历到叶子节点，继续搜索上级节点 */
    while (!stk.empty() || root) {
        //root及其左子树全部入栈
        while (root) {
            //由于前序遍历为 根左右，则root及其左子树val全部加入结果集合
            res.emplace_back(root->val);
            stk.emplace(root);
            root = root->left;
        }
        //左子树为空，栈顶元素退栈，root指向栈顶元素右子树，继续遍历
        root = stk.top();
        stk.pop();
        root = root->right;
    }

    return res;
}

int main() {
    auto *root = new TreeNode(1);
    root->right = new TreeNode(2);
    root->right->left = new TreeNode(3);

    //使用递归算法
    vector<int> res;
    res = preorderTraversal(root);
    for (auto &x : res) {
        cout << x << " ";
    }
    cout << endl;

    //使用迭代算法
    vector<int> res_iter;
    res_iter = preorderTraversal_Iteratively(root);
    for (auto &x : res_iter) {
        cout << x << " ";
    }
    cout << endl;
}